package com.ls.day11;

import com.ls.day2.ListNode;

import java.util.Collections;

public class MergeKLists {
    public ListNode mergeKLists(ListNode[] lists){
        if (lists.length==0)return null;
        if (lists.length==1)return lists[0];

        ListNode list = lists[0];
        for (int i=1;i<lists.length;i++){
            if (lists[i]!=null)
            list = merge(list,lists[i]);
        }
        return list;
    }

    public ListNode merge(ListNode l1,ListNode l2){
        if (l1==null)return l2;
        ListNode p=l1,q=l2,s;
        boolean flag=true;
        if (p.val<q.val){
            s=p;
            p=p.next;
        }else{
            s=q;
            q=q.next;
            flag=false;
        }
        while (p!=null&&q!=null){
            if (p.val<q.val){
                s.next=p;
                s=p;
                p=p.next;
            }else{
                s.next=q;
                s=q;
                q=q.next;
            }
        }
        if (p==null)s.next=q;
        else s.next=p;
        return flag?l1:l2;
    }
}
